perm filename AGENDA.TEX[AM,DBL] blob
sn#394270 filedate 1978-11-14 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00007 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \NSECP{AGENDA}
C00006 00003 \SSEC{AM's Search}
C00018 00004 \SSEC{Constraining AM's Search}
C00025 00005 \SSEC{The Agenda}
C00026 00006 \SSSEC{Why an Agenda?}
C00031 00007 \SSSEC{Details of the Agenda scheme}
C00039 ENDMK
C⊗;
\NSECP{AGENDA}
\qq{`Objectively' given, `important' problems may arise [in math].
But even then the mathematician
is essentially free to take it or leave it and turn to something else, while
an `important' problem in [any other science] is usually a conflict, a contradiction,
which `must' be resolved. The mathematician has a wide choice of which way to turn,
and he enjoys a very considerable freedom in what he does.}{von Neumann}
Section 3.1 will give the reader a feeling for the immensity
of AM's search space. This is the ``problem". The next section will give the
top-level ``solution": the flow of control is governed by a job-list,
an agenda of plausible tasks. Section 3.3 will present some
details of this global control scheme.
Chapter 4 deals with the way AM's heuristics operate; this
could be viewed as the ``low-level" or \4local\0 control structure of
AM.
\SSEC{AM's Search}
\qq{To develop mathematics, one must always labor to substitute ideas for
calculations.}{Dirichlet}
Let's first spend a paragraph reviewing how concepts are stored. AM
contains a collection of data structures, called \4concepts\1. Each
concept is meant to coincide intuitively with one mathematical idea
(e.g., Sets, Union, Trichotomy). As such, a concept has several
aspects or parts, called \4facets\0 (e.g., Examples, Definitions,
Domain/range, Worth). If you wish to think of a concept as a
``frame", then its facets are ``slots" to be filled in. Each facet of
a concept will either be totally blank, or else will contain a bunch
of \4entries\1. For example, the Algorithms facet of the concept
Union may point to several equivalent LISP functions, each of which
can be used to form the union of two sets\foo { The reasons for having
multiple algorithms is that sometimes AM will want one that is fast,
sometimes AM will be more concerned with economizing on storage,
sometimes AM will want to ``analyze" an algorithm, and for that
purpose it must be a very un-optimized function, etc. }. Even the
``heuristic rules" are merely entries on the appropriate kind of facet
(e.g., the entries on the Interest facet of the Structure concept are
rules for judging the interestingness of Structures\foo { A typical such
rule is: ``{\sl A structure is very interesting if all its elements are
mildly interesting in precisely the same way.}" }).
At any moment, AM contains a couple hundred concepts, each of which
has only \4some\0 of its facets filled in. AM starts with 115
concepts, and grows to about 300 concepts before running out of
time/space. Most facets of most concepts are totally blank. AM's
basic activity is to select some facet of some concept, and then try
to fill in some entries for that slot\foo { This is not quite complete.
In addition to filling in entries for a given facet/concept pair, AM
may wish to check it, split it up, reorganize it, etc. }. Thus the
primitive kind of ``\4task\0'' for AM is to deal with a particular
facet/concept pair. A typical task looks like this:
\hjust{\hfill\inbox{\inbox{\hjust{\bf Check the
entries on the ``Domain/range" facet of the ``Bag-Insert"
concept}}}\hfill}
If the average concept has ten or twenty blank facets, and there are
a couple hundred concepts, then clearly there will be about
20x200=4000 ``fill-in" type tasks for AM to work on, at any given
moment. If several hundred facets have recently been filled in,
there will be that many ``check-entries" type tasks available.
Executing a task happens to take around ten or twenty cpu seconds, so over the course of
a few hours
only a small percentage of these tasks can ever be executed.\foo { The precise
``18 seconds average"
figure is not important. All heuristic-search programs
suffer this same
handicap: As the depth to which they've searched increases, the percentage of
nodes (at or above that level) which have been examined {\it decreases}
exponentially (assuming the branching factor b is strictly larger than unity).
}
Since most of these tasks will never be explored, what will make AM
appear smart -- or stupid -- are its choices of which task to pick at
each moment.\foo {
This is true of all heuristic search programs. The branchier the search,
the more it applies.
} So it's worth AM's spending a nontrivial amount of time
deciding which task to execute next. On the other hand, it had better
not be \4too\0 much time, since a task does take only a dozen seconds.\foo {
The answer is that AM spends this ``deciding" time not
just before a task is {\it picked}, but rather each time a task is added to
the agenda. A little under 1 cpu second is spent, on the average, to place the
task properly on the agenda, to assign it a meaningful numeric priority value.
So ``action time" is roughly one order of magnitude larger than ``deciding time". }
One question that must be answered is: What percentage of AM's legal
moves (at any typical moment) would be considered intelligent
choices, and what percentage would be irrational? The answer comes
from empirical results. The percentages vary wildly depending on the
previous few tasks. Sometimes, AM will be obviously ``in the middle"
of a sequence of tasks, and only one or two of the legal tasks would
seem plausible. Other times, AM has just completed an investigation
by running into dead-ends, and there may be hundreds of tasks it
could choose and not be criticized. The median case would perhaps
permit about 6 of the legal tasks to be judged reasonable.
It is important for AM to locate one of these currently-plausible
tasks, but it's not worth spending much time deciding which of
\4them\0 to work on next. AM still faces a huge search: find one of
the 6 winners out of a few thousand candidates.
Its choice of tasks is made even more important due to the 10-second
``cycle time" -- the time to investigate/execute one task. A human
user is watching, and ten seconds is a nontrivial amount of time to
him. He can therefore observe, perceive, and analyze each and every
task that AM selects. Even just a few bizarre choices will greatly
lower his opinion of AM's intelligence. The trace of AM's actions is
what counts, not its final results. So AM can't draw much of its
apparent intelligence from the \4speed\0 of the computer.
Chess-playing programs have had to face the dilemma of the trade-off
between ``intelligence" (foresight, inference, processing,...) and
total number of board situations examined. In chess, the
characteristics of current-day machines, language power \4vs.\0 speed,
and (to some extent) the limitations of our understanding of how to be
sophisticated,
have to date unfortunately
still favored fast, nearly-blind\foo { i.e., using a very simple static
evaluation function. } search. Although machine speed and LISP slowness
may allow
blind search to win over symbolic inference for \4shallow\0 searches,
it can't provide any more than a constant speed-up factor for an
exponential search. Inference is slowly gaining on brute force,\foo { E.g.,
see [Berliner 74]. There, searching is used mainly to verify plausible
moves (a convergent process),
not to discover them (a bushier search).} and must someday triumph.
Since the number of ``legal moves" for AM at any moment is in the
thousands, it is unrealistic to consider ``systematically"\foo { e.g.,
exhaustively, or using αααβ minimaxing, etc. } walking through the
entire space that AM can reach. In AM's problem domain, there is so
much ``freedom" that symbolic inference finally \4can\0 win over the
``simple but fast" exploration strategy\foo { This is the author's
opinion, partially supported by the results of AM. Paul Cohen
disagrees, feeling that machine speed should be the key to an
automated mathematician's success. }.
\SSEC{Constraining AM's Search}
\qq{There exist too many combinations to consider all combinations of existing entities;
the creative mind must only {\sl propose} those of potential interest.}{Poincar\'e}
A great deal of heuristic knowledge is required to
constrain the necessary processing effectively, to zero in on a good task
to tackle
next. This is done in two stages.
\textindent{1.} A list of plausible facet/concept pairs is maintained. Nothing can
get onto this list unless there is some reason why filling in (or checking) that
facet of that concept would be worthwhile.
\textindent{2.} All the plausible tasks on this ``job list" are ranked by the
number and strength of the different reasons supporting them. Thus
the facet/concept pairs near the top of the list will all be very
promising tasks to work on.
The first of these constraints is akin to replacing a \4legal\0 move
generator by a \4plausible\0 move generator. The second kind of
constraint is akin to using a heuristic evaluation function to select
the best move from among the plausible ones.\foo {
Past AI programs (e.g., [Samuel 67]) have indicated that
constraining generation (stage 1, above) is more important than sophisticated
ordering of the resultant candidates (stage 2).
This was confirmed by the experiments performed on AM. }
The job-list or \4agenda\0 is a data structure which is a natural way
to store the results of these procedures. It is (1) a list of all
the plausible tasks which have been generated, and (2) it is kept
ordered by the numeric estimate of how worthwhile each task is. A
typical entry on the agenda might look like this:
\vfill
\yskip
{\eightpoint \:> \parskip 1pt \lineskip 1pt \parindent 0pt
\hjust{\ \ \ Fill in the EXAMPLES facet of the PRIMES concept }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ {\it Reasons for filling in this facet}}
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\↓$ }
\par\hangindent 30pt for 1 {\6 1. No examples of primes are known so far.}
\par\hangindent 30pt for 1 {\6 2. Focus of attention: AM just defined Primes.}
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$\ {\it Overall value of these reasons}}
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\↓$ }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\2250}}
}
\tenpoint \parindent 19pt
While the top task is being executed, some new tasks might get
proposed and merged into the agenda. Also, some new concepts might
get created, and this, too, would generate a flurry of new tasks.
After AM stops filling in entries for the facet specified in the
chosen task, it removes that task from the agenda, and moves on to
work on whichever task is the highest-rated at that time.
The reader probably has a dozen good
questions in mind
at this point (e.g., How do the reasons get rated?, How do the tasks
get proposed?, What happens after a task is selected?,...). The next
section should answer most of these. Some more judgmental ones (How
dare you propose a numeric calculus of plausible reasoning?! If you
slightly de-tune all those numbers, does the system's performance
fall apart?...) will be answered in Chapter 7.
\SSEC{The Agenda}
\qq{Creative energy is used mainly to ask the right question.}{Halmos}
\SSSEC{Why an Agenda?}
This subsection provides motivation for the following one, by arguing
that a job-list scheme is a natural mechanism to use to manage the
task-selection problem AM faces.
Recall that AM must zero in on one
of the best few tasks to perform next, and it repeatedly makes this
choice. At each moment, there might be thousands of directions to
explore (plausible tasks to consider).
If all the legal tasks were written out, and reasons were thought up
to support each one, then perhaps we could order them by the strength
of those reasons, and thereby settle on the ``best" task to work on
next. In order to appear ``smart" to the human user, AM should
\4never\0 execute a task having no reasons attached.
For the moment, assume some magical function exists, which provides
a numeric rating, a priority value, for any given task. The function
looks at a given facet/concept pair, examines all the associated
reasons supporting that task, and computes an estimate of how worthwhile it would be
for AM to spend some time now working on that facet of that concept.
So AM will maintain a list of those legal tasks which have some good
reasons tacked onto them, which justify why each task should be
executed, why it is plausible. At least implicitly, AM has a numeric
rating for each task.
Give or take a few features, this notion of a ``job-list" is the one
which AM uses. It is also called an \4agenda\1.\foo { Borrowed from
Kaplan's term for the job-list present in KRL0 (see
[Bobrow & Winograd 77]).
For an earlier general discussion of agendas, see [Knuth 68]. }
``A task on the agenda" is the same as ``a job on the job-list" is the
same as ``a facet/concept pair which has been proposed" is the same as
``an active node in the search space". Henceforth, I'll use the
following all interchangeably: task, facet/concept pair, node,
job.\foo { Each of these terms will conjure up a
slightly different image: a ``job" is something to do, a ``node" is an
item in a search space, ``facet/concept pair" reminds you of the
format of a task. }.
The flavor of agenda-list used here is analogous to the control structure of
HEARSAY-II [Lesser/Fennell/Erman/Reddy 75]. Vast numbers of tasks are proposed and added
to the job-list. Occasionally, when some new data arrives,
some task is repositioned.
\SSSEC{Details of the Agenda scheme}
At each moment, AM has many plausible tasks (hundreds or even thousands) which
have been suggested for some good reason or other, but haven't been
carried out yet. Each task is at the level of working on a certain
facet of a certain concept: filling it in, checking it, etc. Recall
that each task also has tacked onto it a list of symbolic reasons
explaining why the task is worth doing.
In addition, a number (between 0 and 1000) is attached \4to each
reason\1, representing some absolute measure of the value of that
reason (at the moment).
One global formula\foo { Here is that formula:
$Worth(J) = \|\sqrt{\Sigma R↓i↑2}\| \times (0.2\times Worth(A)\ +
0.3\times Worth(F)\ + 0.5\times Worth(C))$, where J = job to be judged = (Act A,
Facet F, Concept C), and $\{R↓i\}$ are the ratings of the reasons
supporting J. For the sample job pictured in the box below, A=Fillin,
F=Examples, C=Sets, $\{R↓i\}=\{100,100,200\}$. The formula will be repeated --
and explained -- in Section 4.3.} combines
all the reasons' values into a single priority
value for the task as a whole.
This overall rating is taken to indicate how worthwhile it would be for
AM to bother executing that task, how interesting the task
would probably turn out to be.
The ``intelligence" of AM's selection of task is thus seen
to depend on this one formula.
Yet experiments
show
that its precise form is not important. We conclude
that the ``intelligence" has been pushed down into the careful
assigning of reasons (and \4their\0 values) for each proposed task.
\eject %Note this may change if spacing, etc. change
A typical entry on the agenda might look like this:
{\eightpoint \:> \parskip 1pt \lineskip 1pt \parindent 0pt
\hjust{\ \ \ TASK: Fill-in examples of Sets }
\par \hjust{\ \ \ PRIORITY: 300 }
\par \hjust{\ \ \ REASONS: }
\par \hjust{\ \ \ \ \ \ \ \ 100: No known examples for Sets so far. }
\par \hjust{\ \ \ \ \ \ \ \ 100: Failed to fillin examples of Set-union, for lack of examples of Sets }
\par \hjust{\ \ \ \ \ \ \ \ 200: Focus of attention: AM recently worked on the concept of Set-union }
}
\tenpoint \parindent 19pt
Notice the similarity of this to the initial few lines which AM types
just after it selects a job to work on.
The priority value of a task serves a dual purpose: First, it
is used to determine which task on the agenda is the most promising
one to work on next. Second, once a task has been chosen, that
task's
priority value
then is used as an estimate of how much time and space it deserves. The
sample task above might rate 20 cpu seconds, and 200 list cells. When
either of these resources is used up, AM terminates work on the
task, and proceeds to pick a new one.
These two limits will be referred to in the sequel as ``\4time/space quanta\1"
which are allocated to the chosen task.
Whenever several techniques exist for satisfying some task, the remaining
time/space quanta are divided evenly among those alternatives; i.e., each
method is tried for a small time. This policy of parceling out time and space quanta is
called ``activation energy" in [Hewitt 76] and called
``resource-limited processes" in [Norman & Bobrow 75].
In the case of filling in
examples of sets, the space quantum (200 cells) will be used up quickly
(long before the 20 seconds expire).
\yskip
There are two big questions now:
\vskip 2 pt
{\parskip 1pt \lineskip 1pt \parindent 8pt
\hjust{$\bullet$ \ \ Exactly how is a task proposed and ranked? }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ How is a plausible new task first formulated? }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ How do the supporting reasons for the task get assigned? }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ How does each reason get assigned an absolute numeric rating? }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ Does a task's priority value change? When and how? }
\par \hjust{$\bullet$ \ \ How does AM execute a task, once it's chosen? }
\par \hjust{\ \ \ \ \ \ \ \ \ \ \ Exactly what can be done during a task's execution? }
}
\tenpoint \parindent 19pt
\noindent {The next chapter will deal with both of these questions.}